Date: Tue, 05 Nov 1996 20:52:29 GMT
Server: NCSA/1.5
Content-type: text/html
Last-modified: Fri, 25 Oct 1996 14:39:29 GMT
Content-length: 3556

<html>
  <head>

    <title>Fall 1996 Lecture Schedule</title>
    <base href="http://www.cs.wisc.edu/~cs520-1/sched_f96.html">

  </head>

  <body>

    <h1>
      Fall 1996 Lecture Schedule
    </h1>

      This schedule is tentative, but the date of the mid-term examination
      is now set in stone.  The pace after the midterm may be slower than
      outlined here.
      (Some of the topics scheduled near the end of the semester have been
      chosen so they can be dropped without adverse affects.)
      <p>

      The <!WA0><!WA0><!WA0><!WA0><a href="http://www.cs.wisc.edu/~cs520-1/sched_f96.old.html">previous</a> tentative schedule
      is still available.
      <p>

    <table border>
    <tr><th>lecture</th>
        <th>topic</th>
    </tr>

    <tr></tr>

    <tr><td>21 Oct</td>
        <td>proving languages non-Context-free</td>
    </tr>
    <tr><td>23 Oct</td>
        <td>more non-Context-freeness, decision problems for CFLs</td>
    </tr>
    <tr><td>25 Oct</td>
        <td>Post Machines, Recursive and Recursively Enumerable languages</td>
    </tr>

    <tr></tr>

    <tr><td>28 Oct</td>
        <td>Church's thesis, the Chomsky hierarchy, review</td>
    </tr>
    <tr><td>30 Oct</td>
        <td><b>mid-term examination</b>
               (room <font color=Maroon>168 Noland</font>,
               your choice of <font color=Maroon>12:20-2:20</font>
               or <font color=Maroon>1:10-3:10</font>)
               </td>
    </tr>
    <tr><td>&nbsp;1 Nov</td>
        <td>Turing Machines</td>
    </tr>

    <tr></tr>

    <tr><td>&nbsp;4 Nov</td>
        <td>more TMs</td>
    </tr>
    <tr><td>&nbsp;6 Nov</td>
        <td>equivalence of PMs and TMs</td>
    </tr>
    <tr><td>&nbsp;8 Nov</td>
        <td>more Recursive and Recursively Enumerable languages</td>
    </tr>

    <tr></tr>

    <tr><td>11 Nov</td>
        <td>Universal Grammars and Context Sensitive Grammars</td>
    </tr>
    <tr><td>13 Nov</td>
        <td>equivalence of deterministic and nondeterministic TMs</td>
    </tr>
    <tr><td>15 Nov</td>
        <td>proving languages non-Recusively-Enumerable</td>
    </tr>

    <tr></tr>

    <tr><td>18 Nov</td>
        <td>more non-RE languages</td>
    </tr>
    <tr><td>20 Nov</td>
        <td>decision problems for TMs</td>
    </tr>
    <tr><td>22 Nov</td>
        <td>more TM decision problems, Rice's theorem</td>
    </tr>

    <tr></tr>

    <tr><td>25 Nov</td>
        <td>restricted TMs</td>
    </tr>
    <tr><td>27 Nov</td>
        <td>more Chomsky hierarchy</td>
    </tr>
    <!--
    <tr><td>29 Nov</td>
        <td>no class -- Thanksgiving Recess</td>
    </tr>
    -->

    <tr></tr>

    <tr><td>&nbsp;2 Dec</td>
        <td>Alternation in automata</td>
    </tr>
    <tr><td>&nbsp;4 Dec</td>
        <td>more Alternation</td>
    </tr>
    <tr><td>&nbsp;6 Dec</td>
        <td>P and NP</td>
    </tr>

    <tr></tr>

    <tr><td>&nbsp;9 Dec</td>
        <td>more P and NP, NP-completeness</td>
    </tr>
    <tr><td>11 Dec</td>
        <td>Lambda Calculus</td>
    </tr>
    <tr><td>13 Dec</td>
        <td>review</td>
    </tr>

    <tr></tr>

    <tr><td>16 Dec</td>
        <td><b>final examination</b>, 2:45pm, room TBA</td>
    </tr>

    </table>

    <hr>

    <address>
    Fall 1996 Lecture Schedule / 21 October 1996  / Brian Cole
    </address><p>

    &lt;<!WA1><!WA1><!WA1><!WA1><a href="http://www.cs.wisc.edu/~cs520-1/">
      cs520 home page</a>&gt
    &lt;<!WA2><!WA2><!WA2><!WA2><a href="http://www.cs.wisc.edu/">
      UW-Madison Computer Sciences home page</a>&gt
    &lt;<!WA3><!WA3><!WA3><!WA3><a href="http://www.wisc.edu/">
      UW-Madison home page</a>&gt

  </body>
</html>


